/*
*
给你一个整数数组 rewardValues，长度为 n，代表奖励的值。

最初，你的总奖励 x 为 0，所有下标都是 未标记 的。你可以执行以下操作 任意次 ：

从区间 [0, n - 1] 中选择一个 未标记 的下标 i。
如果 rewardValues[i] 大于 你当前的总奖励 x，则将 rewardValues[i] 加到 x 上（即 x = x + rewardValues[i]），并 标记 下标 i。
以整数形式返回执行最优操作能够获得的 最大 总奖励。

示例 1：

输入：rewardValues = [1,1,3,3]

输出：4

解释：

依次标记下标 0 和 2，总奖励为 4，这是可获得的最大值。

示例 2：

输入：rewardValues = [1,6,4,3,2]

输出：11

解释：

依次标记下标 0、2 和 1。总奖励为 11，这是可获得的最大值。

提示：

1 <= rewardValues.length <= 5 * 104
1 <= rewardValues[i] <= 5 * 104

  - @author ala
  - @date 2024-10-09 11:23
*/
package main

import (
	"fmt"
	"math/big"
	"sort"
)

func main() {
	rvs := []int{1, 1, 3, 3}
	//rvs := []int{1, 6, 4, 3, 2}

	fmt.Println(maxTotalReward(rvs))
}

func maxTotalReward(rewardValues []int) int {
	return V1(rewardValues)
}

/**
 *	1）dp[i] = big.NewInt 表示前i个数能否到达j
 *		big.NewInt的每个二进制表示能否到达
 *	2）dp[i-1]左移v位，or给dp[i]
 *	3）dp[N]的二进制长度就是答案
 */
func V1(rvs []int) int {
	//	去重，排序
	set, nums, mx := make(map[int]struct{}, len(rvs)), make([]int, 0, len(rvs)), 0
	for _, n := range rvs {
		if _, ex := set[n]; !ex {
			set[n] = struct{}{}
			nums = append(nums, n)
			mx = max(mx, n)
		}
	}
	//	检测set中是否包含mx-1，或两数和 == mx-1
	set = map[int]struct{}{}
	set[0] = struct{}{}
	for _, n := range nums {
		if _, ex := set[mx-1-n]; ex {
			return mx<<1 - 1
		}
		set[n] = struct{}{}
	}
	//	排序
	sort.Ints(nums)

	//	逐位dp
	dp, one := big.NewInt(1), big.NewInt(1)
	for _, n := range nums {
		p := new(big.Int)
		mask := p.Sub(p.Lsh(one, uint(n)), one)
		mask = p.Lsh(p.And(dp, mask), uint(n))
		dp.Or(dp, mask)
	}
	return dp.BitLen() - 1
}
